#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "strmap.h"

//Número de threads lançadas pelo OpenMP
#define OMP_THREADS 4
//Tamanho máximo de palavras geradas aleatoriamente (sem combinação)
#define MAX_LENGTH 5

//Aloca memoria, finaliza o programa em caso de erro
void* allocate(int bytes);
//Verifica resultado de retorno de função MPI
void check_status(int status);
//Verifica se a palavra contém espaço ou caracteres inválidos. Permite
//palavras com hífen
int valid_word(char *word);

int main(int argc, char* argv[])
{
   struct timeval ti, tf;
   long int sec, usec;
   
   //Início da contagem de tempo
   gettimeofday(&ti, NULL);

   int rank, size, slaves;       //Variáveis relevantes ao MPI
   int i, j, tag = 1;
   int n_words;
   char *text;
	MPI_Request *handle;
   StrMap *sm;                   //Tabela hash para verificação de palavras
   
   //Inicializa MPI e variáveis relevantes à execução de todo o programa
   MPI_Init(&argc, &argv);
   MPI_Comm_rank (MPI_COMM_WORLD, &rank);
   MPI_Comm_size (MPI_COMM_WORLD, &size); 
   slaves = size - 1;
   handle = (MPI_Request*) allocate(slaves * sizeof(MPI_Request));
   
   omp_set_num_threads(OMP_THREADS);
   
   /* Nó Mestre */
   if(rank == 0)
   {
      FILE *fp;
      int text_size, *words_slaves_size, words_found;
      char *aux;
      
      //Determina o tamanho do arquivo
      fp = fopen("palavras.txt", "rb");
      fseek(fp, 0L, SEEK_END);
      text_size = ftell(fp);
      rewind(fp);
      
      //Lê o texto em memória como uma única string
      text = (char*) allocate((text_size + 1) * sizeof(char));
      if(fread(text, 1, text_size, fp) != text_size)
      {
         printf("Erro na leitura do arquivo.\n");
         exit(0);
      }
      text[text_size] = '\0';
      
      for(i = 0; i < text_size; i++)
         text[i] = tolower(text[i]);
      //Envia o tamanho dos buffers para cada nó escravo
      for(i = 1; i <= slaves; i++)
         MPI_Isend(&text_size, 1, MPI_INT, i, tag, MPI_COMM_WORLD, handle);
      //Envia o conteúdo dos buffers para cada nó escravo
      for(i = 1; i <= slaves; i++)
         MPI_Isend(text, text_size, MPI_CHAR, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));

      //Conta o número de palavras válidas no texto
      sm = sm_new(text_size);
      aux = strtok(text, ",\n\r");
      for(n_words = 0; aux != NULL;)
      {
         if(valid_word(aux) && !sm_exists(sm, aux))
         {
            n_words++;
            sm_put(sm, aux, "");
         }
         aux = strtok(NULL, ",\n\r");
      }
      //Envia o número de palavras para os escravos
      for(j = 1; j <= slaves; j++)
         MPI_Isend(&n_words, 1, MPI_INT, j, tag, MPI_COMM_WORLD, handle);

      //Recebe o número de palavras de até 5 caracteres de cada escravo
      words_slaves_size = (int*) allocate(slaves * sizeof(int));
      for(i = 1; i <= slaves; i++)
         MPI_Irecv(&words_slaves_size[i - 1], 1, MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
      //Redução sobre o vetor para determinar as posições de memória para as quais copiar
      for(i = 1; i < slaves; i++)
         words_slaves_size[i] += words_slaves_size[i - 1];
      //Recebe as palavras de até 5 caracteres de cada escravo
      MPI_Irecv(text, words_slaves_size[0], MPI_CHAR, 1, tag, MPI_COMM_WORLD, &handle[0]);
      for(i = 2; i <= slaves; i++)
         MPI_Irecv(&text[words_slaves_size[i - 2]], words_slaves_size[i - 1] - words_slaves_size[i - 2], MPI_CHAR, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
      
      text_size = words_slaves_size[slaves - 1];
      //Envia tamanho do vetor com todas as palavras encontradas para os escravos
      for(i = 1; i <= slaves; i++)
         MPI_Isend(&text_size, 1, MPI_INT, i, tag, MPI_COMM_WORLD, handle);
      //Envia o vetor com todas as palavras encontradas para os escravos
      for(i = 1; i <= slaves; i++)
         MPI_Isend(text, text_size, MPI_CHAR, i, tag, MPI_COMM_WORLD, &handle[i - 1]);

      //Resultado parcial (palavras de até 5 caracteres)
      for(i = 0, words_found = 0; i < text_size; i += strlen(&text[i]) + 1)
         words_found++;
      printf("Palavras encontradas: %d (%.2f%%). ", words_found, 100 * ((float) words_found) / n_words);
      gettimeofday(&tf, NULL);
      sec = tf.tv_sec - ti.tv_sec;
      if(tf.tv_usec < ti.tv_usec)
         sec--;
      usec = (tf.tv_usec - ti.tv_usec + 1000000) % 1000000;
      printf("Tempo decorrido: %ld.%06ld s.\n", sec, usec);
      
      //Recebe palavras formadas por combinações dos escravos
      for(i = 1; i <= slaves; i++)
         MPI_Irecv(&words_slaves_size[i - 1], 1, MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));

      for(i = 1; i < slaves; i++)
         words_slaves_size[i] += words_slaves_size[i - 1];
      
      MPI_Irecv(&text[text_size], words_slaves_size[0], MPI_CHAR, 1, tag, MPI_COMM_WORLD, &handle[0]);
      for(i = 2; i <= slaves; i++)
         MPI_Irecv(&text[text_size + words_slaves_size[i - 2]], words_slaves_size[i - 1] - words_slaves_size[i - 2], MPI_CHAR, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
     
     text_size += words_slaves_size[slaves - 1];
     
     //Resultado final (palavras de até 5 caracteres + combinações)
      for(i = 0, words_found = 0; i < text_size; i += strlen(&text[i]) + 1)
         words_found++;
      printf("Palavras encontradas: %d (%.2f%%). ", words_found, 100 * ((float) words_found) / n_words);
      gettimeofday(&tf, NULL);
      sec = tf.tv_sec - ti.tv_sec;
      if(tf.tv_usec < ti.tv_usec)
         sec--;
      usec = (tf.tv_usec - ti.tv_usec + 1000000) % 1000000;
      printf("Tempo decorrido: %ld.%06ld s.\n", sec, usec);
      
      //for(i = 0; i < text_size; i += strlen(&text[i]) + 1)
      //   printf("%s\n", &text[i]);
   }
   else
   {
      int text_size, length, current_word;
      int word[OMP_THREADS][2 * MAX_LENGTH + 2];
      char print_buffer[OMP_THREADS][2 * MAX_LENGTH + 2];
      char **words, *aux, *aux2;
   
      //Recebe tamanho do buffer para alocar o texto
      MPI_Irecv(&text_size, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));
      
      //Aloca memória e recebe
      text = (char*) allocate((text_size + 1) * sizeof(char));
      MPI_Irecv(text, text_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, handle);
      text[text_size] = '\0';
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));

      MPI_Irecv(&n_words, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));
      
      //Identifica as palavras válidas no texto
      words = (char**) allocate(n_words * sizeof(char*));
      sm = sm_new(n_words);
      aux = strtok(text, ",\n\r");
      for(i = 0; aux != NULL;)
      {
         if(valid_word(aux) && !sm_exists(sm, aux))
         {
            words[i++] = aux;
            sm_put(sm, aux, "");
         }
         else
            n_words--;
         aux = strtok(NULL, ",\n\r");
      }

      //Inicializa a palavra com 'a' em todas as posições, e então aplica um
      //offset baseado no rank do escravo e no número da thread.
      //A busca é realizada adicionando-se um valor numérico (interpretado como
      //um caracter), de modo que todo o espaço do input é coberto e nenhuma
      //combinação é realizada por mais de uma thread ou escravo
      text_size = 0;
      for(length = 1; length <= MAX_LENGTH; length++)
      {
         for(j = 0; j < length; j++)
            for(i = 0; i < OMP_THREADS; i++)
               word[i][j] = 'a';
         for(i = 0; i < OMP_THREADS; i++)
         {
            word[i][length - 1] += i + (rank - 1) * OMP_THREADS;
            word[i][length] = '\0';
         }
         
         for(j = length - 1; j > 0; j--)
         {
            while(word[i][j] > 'z')
            {
               word[i][j] -= 'z' - 'a' + 1;
               word[i][j - 1] += 1;
            }
         } 
         
         #pragma omp parallel for private(j)
         for(i = 0; i < OMP_THREADS; i++)
            while(word[i][0] <= 'z')
            {
               for(j = 0; word[i][j] != '\0'; j++)
                  print_buffer[i][j] = (char) word[i][j];
               print_buffer[i][j] = '\0';

               //Seção crítica: encontrou-se uma palavra, adiciona-a
               //à tabela hash e ao buffer de envio
               if(sm_exists(sm, print_buffer[i]))
               #pragma omp critical
               {
                  strcpy(&text[text_size], print_buffer[i]);
                  text_size += strlen(print_buffer[i]) + 1;
               }
                  
               
               word[i][length - 1] += slaves * OMP_THREADS;
               for(j = length - 1; j > 0; j--)
               {
                  while(word[i][j] > 'z')
                  {
                     word[i][j] -= 'z' - 'a' + 1;
                     word[i][j - 1] += 1;
                  }
               }
            }
      }

      //Envia palavras de até 5 caracteres ao mestre
      MPI_Isend(&text_size, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      MPI_Isend(text, text_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, handle);

      //Recebe todas as palavras de até 5 caracteres do mestre
      MPI_Irecv(&text_size, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));
      MPI_Irecv(text, text_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, handle);
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));

      //Verifica o número de palavras total
      for(i = 0, n_words = 0; i < text_size; i += strlen(&text[i]) + 1)
         words[n_words++] = &text[i];
      
      //Repete o processo, porém agora tentando combinações de palavras já
      //encontradas em vez de palavras geradas randomicamente. Tentam-se
      //combinações de 2 palavras justapostas em qualquer ordem, separadas ou
      //não por hífen.
      aux = &text[text_size];
      aux2 = aux;
      text_size = 0;
      #pragma omp parallel for private(j, current_word, print_buffer)
      for(i = 0; i < OMP_THREADS; i++)
      {
         current_word = i + (rank - 1) * OMP_THREADS;
         while(current_word < n_words)
         {
            for(j = current_word + 1; j < n_words; j++)
               if(strlen(words[current_word]) + strlen(words[j]) > MAX_LENGTH)
               {
                  strcpy(print_buffer[i], words[current_word]);
                  strcat(print_buffer[i], words[j]);
                  
                  if(sm_exists(sm, print_buffer[i]))
                  #pragma omp critical
                  {
                     strcpy(aux2, print_buffer[i]);
                     text_size += strlen(print_buffer[i]) + 1;
                     aux2 = &aux[text_size];
                  }
                  
                  strcpy(print_buffer[i], words[current_word]);
                  strcat(print_buffer[i], "-");
                  strcat(print_buffer[i], words[j]);
                  
                  if(sm_exists(sm, print_buffer[i]))
                  #pragma omp critical
                  {
                     strcpy(aux2, print_buffer[i]);
                     text_size += strlen(print_buffer[i]) + 1;
                     aux2 = &aux[text_size];
                  }
                  
                  strcpy(print_buffer[i], words[j]);
                  strcat(print_buffer[i], words[current_word]);
                  
                  if(sm_exists(sm, print_buffer[i]))
                  #pragma omp critical
                  {
                     strcpy(aux2, print_buffer[i]);
                     text_size += strlen(print_buffer[i]) + 1;
                     aux2 = &aux[text_size];
                  }
                  
                  strcpy(print_buffer[i], words[j]);
                  strcat(print_buffer[i], "-");
                  strcat(print_buffer[i], words[current_word]);
                  
                  if(sm_exists(sm, print_buffer[i]))
                  #pragma omp critical
                  {
                     strcpy(aux2, print_buffer[i]);
                     text_size += strlen(print_buffer[i]) + 1;
                     aux2 = &aux[text_size];
                  }
               }
            current_word += slaves * OMP_THREADS;
         }
      }
      
      //Envia o resultado para o mestre
      MPI_Isend(&text_size, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      MPI_Isend(aux, text_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, handle);
   }
   
   MPI_Finalize();
   return 0;
}



//Aloca memoria, finaliza o programa em caso de erro
void* allocate(int bytes)
{
   void *ptr;
   
   ptr = malloc(bytes);
   if(ptr == NULL)
   {
      printf("Erro na alocação de memória.\n");
      exit(0);
   }
   
   return ptr;
}

//Verifica resultado de retorno de função MPI
void check_status(int status)
{
   if(status != MPI_SUCCESS)
   {
      printf("Erro na comunicação MPI.\n");
      exit(0);
   }
}

//Verifica se a palavra contém espaço ou caracteres inválidos. Permite
//palavras com hífen
int valid_word(char *word)
{
   int i;
   
   if(strlen(word) > 2 * MAX_LENGTH + 1)
      return 0;
   for(i = 0; i < strlen(word); i++)
      if((word[i] < 'a' || word[i] > 'z') && word[i] != '-')
         return 0;
   return 1;
}
